\section{Introduction}
\label{sec:intro}
A number of real world applications can be modeled as diffusion
processes over networks. Some prominent examples include diseases
transmitted among humans, viruses transmitted over computer networks,
information/ideas spread over contact networks, and creation of
friendships through social networks. Despite the diversity among these
applications, there are lots of fundamental similarities in the
mathematical models. Understanding the dynamics of these mathematical
models can help us anticipate, exploit, and control the propagation
processes.

A lot of interesting questions could be asked about the
dynamics. Consider human disease or computer virus transmission for
example. Will it become an epidemic? How much time does it take to
become an epidemic? Who will get infected? What's the social cost of
the epidemic? Once we understand all these, we could design
interventions to control the dynamics. For instance, how do we
vaccinate or quarantine the population so that the epidemic is
controlled? How do we secure computers to enhance the network
resilience? What polices should be applied with budget constraints
(limited vaccines or anti-virus software licenses), how should we
distribute resources, and how much can we reduce the social cost?
Often these interventions can be translated into voluntary directives
from government, like take vaccines or stay at home. However, people
usually don't adhere to such recommendations. Instead, they make
decisions based on their specific utilities and objectives. Such
decisions happen in a decentralized manner, which makes game theory a
natural approach to study these problems. Moreover, people alter their
contacts dynamically. For example, a vaccinated person may increase
his/her contacts with friends, due to perceived secure feelings. These
behavioral changes have a huge impact on the dynamics and the
effectiveness of these interventions, so that ``good'' intervention
strategies might be ineffective, depending on the behavioral
changes. All these make the analysis of dynamically changing networks
more interesting and challenging.

We classify our research work into the following two
categories. First, we design and analyze efficient distributed
algorithms for positive diffusion processes over dynamically changing
networks. We introduce our work in Section
\ref{sec:diffusiontime-intro}, and state detailed results and proposed
research in Section \ref{sec:diffusiontime}. Secondly, we study
intervention strategies for harmful diffusion processes. This is
extremely important when we deal with diseases, viruses, or other
harmful information. Not only do we need to know when there is an
epidemic, but also we should be able to design good intervention
strategies to reduce our loss. We introduce this line of work in
Section \ref{sec:intervention-intro}, and state detailed results and
proposed research in Section \ref{sec:intervention}.

\subsection{Distributed algorithms for positive diffusions}
\label{sec:diffusiontime-intro}
In peer-to-peer (P2P), wireless, and sensor networks, how to spread
information efficiently in a distributed manner is an important
problem. Thus, designing simple (easy to implement and deploy)
distributed algorithms, that provide a good guarantee on the spreading
time, is crucial for the success of such systems. Indeed, a huge body
of research work has been devoted to this area
\cite{karp+ssv:rumor,feige+pru:broadcast,pittel:rumor,boyd+gps:gossip,elsasser+s:broadcast,kempe+k:gossip,ganesh05,wang03}. However,
the vast majority study and analyze the diffusion processes defined on
static networks. In many P2P, wireless, and sensor networks, however,
the underlying communication links may be broken temporarily, and
users/nodes may join and leave over time. Only recently has there been
some work considering diffusion over dynamic adversarial networks
\cite{avin+kl:dynamic,kuhn+lo:dynamic}. Therefore, we propose and
analyze several distributed algorithms over different kinds of
dynamically changing networks. First we consider the case where
networks are changed by the diffusion process itself. A canonical
example of such a network is resource discovery problem, which is
introduced in Section \ref{sec:intro-resource}. The second dynamic
model we consider is the adversary networks. We study token
dissemination problem under such dynamics, which is introduced in
Section \ref{sec:intro-token}.

\subsubsection{Resource discovery}
\label{sec:intro-resource}
When a P2P network is formed, the first task for a node is to discover
all the other available nodes on the network. We refer such problem as
{\em resource discovery}. Designing good distributed algorithms for
resource discovery can improve the efficiency and scalability of these
P2P systems.

We model the network as a graph. Each node represents a computer/user
in the network. If node $u$ knows the existence of node $v$ (namely
node $u$ discovered node $v$), then there is an edge between $u$ and
$v$. Each node can only discover new nodes through the nodes he
already knows. Every time $u$ discovers a new node in the network, he
creates an edge to this node. We want to understand how much time it
takes for every node in the network to discover all the nodes.

We propose two ``simple'' distributed algorithms for the resource
discovery problem, {\em triangulation} and {\em 2-hop random walk}. We
run simulations for both algorithms on various families of graphs, and
observe that both of them have good running time (nearly linear
time). Thus, in Section \ref{sec:diffusiontime-resource}, we focus on
proving the following conjecture: the running time for triangulation
and 2-hop random walk algorithms is $O(n\log n)$ on graphs with $n$
nodes.

\subsubsection{Token dissemination}
\label{sec:intro-token}
The token dissemination problem is one of the most popular and well
studied problems in distributed computing. At a high level, it can be
stated as follows. Every node in the network has a piece of
information she wants to spread. The goal is to design an distributed
algorithm that spreads each piece of information to all the other
nodes as efficiently as possible. Most of the studies on the token
dissemination problem have been restricted to static networks, which do
not model the real world very well, especially in the case of wireless
and sensor networks, where the underlying links are not reliable and
nodes can join and leave over time.

Inspired by the works \cite{avin+kl:dynamic,kuhn+lo:dynamic}, we
propose several efficient distributed algorithms for adversary
networks. If the adversary can disconnect the graph, then it is
imposible to disseminate tokens to all nodes. Thus, we require the
graph to be connected at each round of communication. The adversary
can decide how the nodes are connected. Our adversary model is very
general; if we can devise good distributed algorithms under such a
dynamic model, then we can apply them to more restricted dynamic
models.  We conjecture that the {\em randomized token forwarding}
algorithm completes in $O(n\log n)$ time on all graphs.

\junk{
\subsubsection{Diffusion time in dynamic networks}
Diffusion time is one of the most important properties to study in
order to understand the dynamics of diffusion processes. There is a
huge body of work on diffusion time under different models
\cite{karp+ssv:rumor,feige+pru:broadcast,pittel:rumor,boyd+gps:gossip,elsasser+s:broadcast,kempe+k:gossip,ganesh05,wang03}. However,
all of them study the diffusion processes defined on static
networks. Only recently, has there been some work considering
diffusion over dynamic adversarial networks
\cite{avin+kl:dynamic,kuhn+lo:dynamic}.

We study a number of diffusion processes over dynamic networks. First
we look at {\em friendship diffusion process}. With the fast growth of
social networks, such as Facebook, people friend each other through
friends. If we model the social network as a graph: vertices represent
people, and edges represent the friendship relations between
vertices. Once a person becomes a friend with someone else, a new edge
is created in such graph. We want to understand, in such dynamically
changed graphs, how fast can friendship propagate. Such model is not
limited to friendship diffusion over social networks. It can also be
apply to other applications, such as resource discovery in P2P
networks.

Secondly, we study information diffusion over adversarial networks,
which was first proposed in \cite{kuhn+lo:dynamic}. The network
dynamics here is quite different from the friendship diffusion
process. The network is altered by an adversary, not under the control
of our behaviors. In such settings, how fast information can spread,
and how to design efficient distributed algorithms to speed up
diffusion processes are crucial problems.
}

\subsection{Intervention strategies to prevent diffusions}
\label{sec:intervention-intro}
When studying diffusion processes of harmful information (such as
human diseases, computer viruses, gossips, etc.), an important task is
to design good intervention strategies to prevent the diffusion. In
the rest of this proposal, we often use human disease as an example of
harmful information, and vaccination as an intervention example. Thus,
when we talk about diseases and vaccinations, they refer to general
harmful information and interventions.

We propose to study intervention strategies in three different
settings. First, we look at centralized intervention strategies, where
there is a centralized entity that is in charge of distributing
vaccinations to control diseases. Second, we study decentralized
intervention strategies, where individuals decide whether to vaccinate
themselves in a decentralized manner. Lastly, we augment our models
with behavior changes; when an individual is vaccinated, he may apply
certain behavior changes due to the perceived secure feelings, which
will alter the structure of the underlying contact network and hence
have an impact on the diffusion process. We take into account the
impact of change in the behavior of vaccinated individuals in
conjunction with potential failure of the vaccines.

\subsubsection{Centralized intervention strategies}
For many diseases, such as influenza, vaccinations are a commonly used
strategy in controlling the spread. A fundamental question in
mathematical epidemiology is to determine what fraction of the
population needs to be vaccinated in order to eradicate the disease,
and how to allocate a limited supply of vaccines. The key point here
is to identify a set of critical vertices in the graph and secure them,
which could in turn cut the transmission path of diseases. However,
such problems are often NP-hard to solve. Thus, finding efficient
algorithms with good approximation ratios is desired. A lot of research
work has been devoted to solving this problem
\cite{AspnesCY2006,berger+episcalefree05,lelarge+b:security,yang+h1n109,reluga+medlock,kuhlman:pkdd10}.

We generalize the mathematical model proposed in
\cite{AspnesCY2006}. Undirected graph $G$ represents the contact
network between people/computers. For each node in $G$, there is an
intervention cost and infection cost. These costs can vary between
nodes. When a node takes intervention, it cannot be infected any
more. Thus, we remove this node from $G$. A node is chosen randomly
according to some arbitrary distribution to start the infection. Every
other nodes that are in the same connected component will be
infected. The goal is to minimize the sum of each individual's
cost. We improve \cite{AspnesCY2006}'s $O(\log^{1.5} n)$ approximation
ratio to $O(\log n)$. We also back up our theoretical results with
comprehensive simulations over a number of families of graphs, which
shows that, in practice, our approximation algorithm gives a much
better guarantee. These results can provide guidance for government
and network administrators to optimize resource allocation.

\subsubsection{A game-theoretic study of decentralized intervention decisions}
Often times, individuals make decisions based on their specific
utilities and objectives in a decentralized manner. For example, in
the case of disease transmission, individuals decide whether to secure
themselves based on information including perceived infection cost,
prices of vaccines (or antidotes), and decisions of other people. We
use a game theoretic framework for analyzing decentralized intervention.

In our research, we found out that the spread of a disease and the
intervention strategies crucially depend on the amount and quality of
information available to the individuals. The amount of information
available can be characterized by its locality: the distance $d$
within the network up to which information is available to the vertex
($d$-local). Our results in \cite{kumar+rss:icdcs} suggest that $d$
has a big influence on the existence and structure of Nash equilibria
\cite{nash51}. More specifically, our research answers the following
questions. Under what conditions do pure Nash equilibria exist for
intervention games in which the information available to each node is
$d$-local? What is the complexity of finding these equilibria? How
good are these equilibria compared with social optimum in terms of
costs (a.k.a. price of anarchy \cite{koutsoupias99worst})?

\subsubsection{Impact of behavioral changes}
Most vaccines have very limited efficacy (typically 30\% in the case
of influenza). However, people are not very well aware of this
limitation, and often over-estimate the efficacy of vaccines. Indeed,
the perceived protection from infection might cause behavior changes,
leading to an increase in contact by a vaccinated individual. In a
series of important papers \cite{blower+risk94,blower:chapter}, Sally
Blower and her collaborators demonstrated risk behavior change, in the
context of HIV vaccination, could lead to perverse
outcomes. \junk{They demonstrated this effect using a differential
  equation model where the spread of the epidemic is captured using
  the ``reproductive number'' (denoted by $R_0$).}

We study the impact of behavior changes on disease dynamics in
networks and observe (through simulation) a rich and complex behavior
dependent both on the underlying network characteristics as well as
the ``sidedness'' of the risk behavior change. The contact network is
an undirected graph with each edge having a certain probability of
disease transmission. We consider both uniform random vaccination
(where each node is vaccinated independently with the same
probability) as well as targeted vaccination (where nodes are
vaccinated based on their degree of connectivity). Vaccines are
assumed to fail uniformly and randomly. We model risk behavior change
by an increase in the disease transmission probability. A significant
aspect of our work is the consideration of ``sidedness'' of risk
behavior change. We classify diseases as 1-sided or 2-sided based on
whether the increase of disease transmission probability requires an
increase in risk behavior of both the infector and the infectee or
just the infector. As example: influenza (H1N1) may be modeled as
1-sided disease since a vaccinated individual may be motivated to
behave more riskily (going to crowded places, traveling on planes,
etc.), thus increasing the chance of infecting all he comes in contact
with; whereas AIDS (HIV) may be modeled as 2-sided disease since the
increase in disease transmission probability requires both the
individuals participating in the interaction to engage in risky
behavior. Of course, these examples are simplistic and most diseases
have elements of both 1-sided and 2-sided risk behaviors.

With the existence of risk behavior, what would be good intervention
strategies? Is targeted vaccination alway better than random
vaccination? With more intervention resources, are we guaranteed to
have less people infected? In Section \ref{sec:behavioral}, we present
our findings, and propose to prove rigorously what we observed in the
simulation.

\junk{
The two major points of departure of our model from the earlier
differential equation based model are: First, the differential
equation model divides the population into fixed set of groups and
models the interaction between different groups in a uniform way. The
epidemic spread is then characterized by the ``reproductive ratio'',
denoted by $R_0$, with the expected epidemic size exhibiting a
threshold behavior in terms of $R_0$. In contrast, we use a network
model that captures the fine structure of interactions between
individuals rather than groups. The heterogenous network model extends
to a large range of real-life situations. But the increased fidelity
comes at a price. The outcomes are more complicated and varied and the
general approach of lowering $R_0$ does not appear to be directly
applicable.  Secondly, the work of Blower et al does not recognize the
``sidedness'' inherent in risk behavior change. Their work implicitly
assumes a 1-sided risk behavior change where vaccinated individual
engage in risky behavior increasing the changes of infection of those
they come in contact with. Our work explicitly treats both 1-sided and
2-sided risk behavior changes and captures a major difference between
diseases such as influenza on the one hand versus AIDS on the
other. This is much more than just a nuance as we discover that the
sidedness of the risk behavior change may have direct implications for
public policy.
}